package interview.math;

/**
 * 大数相乘
 * 思路：
 * arr数组，每一个位置，记录该位置的数有多少
 * 举栗：
 * 第一个代表个位，那么这个数字代表个位的数字有多少
 * 第二个代表十位，那么这里的数字结果要乘以10
 * 以此类推，所有位的数字加起来，就是最终的结果
 *
 * Created by yzy on 2021-03-01 17:18
 */
public class MultiplyStrings {

    public static void main(String[] args) {
        String num1 = "123";
        String num2 = "456";

        System.out.println(multiply(num1, num2));
    }

    public static String multiply(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[] arr = new int[len1 + len2];
        for(int i=len1-1; i>=0; i--){
            int num1 = str1.charAt(i) - '0';
            for(int j=len2-1; j>=0; j--){
                int num2 = str2.charAt(j) - '0';
                int idx = len1 + len2 - i - j - 2;
                int tmp = num1 * num2;
                arr[idx] = arr[idx] + tmp;
            }
        }

        int carry = 0;
        for(int i=0; i<arr.length; i++){
            int curr = carry + arr[i];
            arr[i] = curr % 10;
            carry = curr / 10;
        }

        StringBuilder bu = new StringBuilder();
        boolean addNum = false;
        for(int i=arr.length-1; i>=0; i--){
            if(arr[i] != 0){
                addNum = true;
            }
            if(addNum) {
                bu.append(arr[i]);
            }
        }

        return bu.length()==0 ? "0" : bu.toString();
    }
}
